package twobranchTree.serialize;

import java.util.LinkedList;

import twobranchTree.preorderTraversal.TreeNode;

/**
 * @Date 2020/03/07
 * @author 王光浩
 * @Thinking 方法与上面的类似，但是进行了改进，没有将给的二叉树构建成一颗完美二叉树，而是对每一个叶子节点以及单子节点的root
 * 			 节点添加null节点。
 * @Analysis 时间复杂度O（n），空间复杂度O（n）
 */
public class MyMethodTwo {
    public String serialize(TreeNode root) {
    	LinkedList<TreeNode> queue=new LinkedList<TreeNode>(); //进行层序遍历的中间工具
    	StringBuilder res=new StringBuilder();
    	if(root==null)return res.toString();
    	queue.add(root);
    	//进行层序遍历
    	while(!queue.isEmpty()) {
    		int size=queue.size();
    		for(int i=0;i<size;i++) { //每层的遍历方法
    			TreeNode tem=queue.poll();
    			if(tem==null) {
    				res.append("null,");
    			}
    			else {
    				res.append(tem.val+",");
    				if(tem.left!=null)queue.add(tem.left);
    				else queue.add(null);
    				if(tem.right!=null)queue.add(tem.right);
    				else queue.add(null);
    			}
    		}
    	}
    	return res.toString();
    }
    //根据当前层，连接下层，并且将下层的所有节点信息加入queue中
    public TreeNode deserialize(String data) {
    	if(data.length()==0)return null;
    	LinkedList<TreeNode> queue=new LinkedList<TreeNode>(); //保存当前层的所有节点
    	int first=0;  //下一个需要访问节点值的首尾位置
    	int last=0;
    	while(data.charAt(last)!=','){ //找到为节点
    		last++;
    	}
    	TreeNode root=new TreeNode(Integer.valueOf(data.substring(first,last)));
    	first=++last;
    	queue.add(root);
    	//进行反序列化
    	while(!queue.isEmpty()) {
    		int size=queue.size();
    		for(int i=0;i<size;i++) {
    			TreeNode tem=queue.poll();
    			if(tem!=null) {
    				//左子树
    				while(data.charAt(last)!=',') 
    					last++;
    				if(data.substring(first,last).equals("null")) {
    					queue.add(null);
    				}
    				else {
    					TreeNode left=new TreeNode(Integer.valueOf(data.substring(first,last)));
    					tem.left=left;
    					queue.add(left);
    				}
    				first=++last;
    				//右子树
    				while(data.charAt(last)!=',') 
    					last++;
    				if(data.substring(first,last).equals("null")) {
    					queue.add(null);
    				}
    				else {
    					TreeNode right=new TreeNode(Integer.valueOf(data.substring(first,last)));
    					tem.right=right;
    					queue.add(right);
    				}
    				first=++last;
    			}
    		}
    	}
    	return root;
    }
}
